Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that: A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Assume that:

    N is an odd integer within the range [1..1,000,000];
    each element of array A is an integer within the range [1..1,000,000,000];
    all but one of the values in A occur an even number of times.

Complexity:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.


Creating sample Array


In [3]:
A = [9,3,9,3,9,7,9]

In [4]:
print len(A)


7

In [8]:
print sorted(A)


[3, 3, 7, 9, 9, 9, 9]

designing algorithm


In [31]:
single_num = sorted(A)[0]
count = 0
if len(A) == 0:
    print A
    
for num in sorted(A):
    print "num: ", num
    
    if num % single_num:
        print "single num: ", single_num
        
        print "count: ", count
        
        if count > 1:
            single_num = num
            count = 0
        else:
            print single_num
            
            break
    
    count += 1
   

#print single_num


num:  3
num:  3
num:  7
single num:  3
count:  2
num:  9
single num:  7
count:  1
7

In [63]:
def solution_1(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 0
            
        for i,num in enumerate(sorted(A)):
            if num != single_num:
                print "num: ", num
                
                print "single num: ", single_num
                
                print "Count: ", count
                
                if count > 1:
                    single_num = num
                    count = 1
                elif count == 1:
                    return single_num
            else:
                count += 1
            if i >= len(A)-1:
                return single_num
            
            print "end single num: ", single_num
            
            print "end count: ", count
            
            print "end num: ", num

In [64]:
print sorted(A), "\n"

print solution(A)


[3, 3, 7, 9, 9, 9, 9] 

end single num:  3
end count:  1
end num:  3
end single num:  3
end count:  2
end num:  3
num:  7
single num:  3
Count:  2
end single num:  7
end count:  1
end num:  7
num:  9
single num:  7
Count:  1
7

In [65]:
B = [2, 2, 3, 3, 4]

In [66]:
print sorted(B), "\n"

print solution(B)


[2, 2, 3, 3, 4] 

end single num:  2
end count:  1
end num:  2
end single num:  2
end count:  2
end num:  2
num:  3
single num:  2
Count:  2
end single num:  3
end count:  1
end num:  3
end single num:  3
end count:  2
end num:  3
num:  4
single num:  3
Count:  2
4

version 2-


In [82]:
def solution_2(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 0
            
        for i,num in enumerate(sorted(A)):
            if num != single_num: 
                print "num: ", num
                
                print "Count: ", count
                
                print "single num: ", single_num
                
                if count > 1:
                    single_num = num
                    
                    count = 1
                
                elif count == 1:
                    return str(single_num) +" " + str(sorted(A[i-5:i+5])) 
            else:
                count += 1
            
            if i >= len(A)-1:
                return single_num

In [83]:
print sorted(B)

print solution_2(B)


[2, 2, 3, 3, 4]
num:  3
Count:  2
single num:  2
num:  4
Count:  2
single num:  3
4

In [84]:
print sorted(A)

print solution_2(A)


[3, 3, 7, 9, 9, 9, 9]
num:  7
Count:  2
single num:  3
num:  9
Count:  1
single num:  7
7 [7, 9]

V3


In [ ]:
def solution_3(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 1
            
        for i,num in enumerate(sorted(A)):
            if num != single_num:    
                if count > 1:
                    single_num = num
                    
                    count = 1
                
                elif count == 1:
                    return single_num
            else:
                count += 1
            
            if i >= len(A)-1:
                return single_num

V4


In [88]:
def solution_4(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 1
            
        for i,num in enumerate(sorted(A)):
            if num != single_num:    
                if count > 1:
                    single_num = num
                    
                    count = 1
                
                elif count == 1:
                    return single_num
            elif single_num == num:
                count += 1
            
            if i >= len(A)-1:
                return single_num

In [93]:
sorted(A)
print A

print solution_4(A)


[3, 3, 7, 9, 9, 9, 9]
7

V 5 - Some where long the lines forgot about the fine line "All but one occurs Even number of times". Instead solved it for "all but one int does not have any pair, is only a single element". Fixing the solutions now.


In [103]:
def solution_5(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 0
            
        for i,num in enumerate(sorted(A)):
            if num != single_num:    
                if count > 1:
                    if count % 2:
                        print "count", count
                        
                        print "num", num
                        
                        print "single num", single_num
                        
                        return single_num
                    
                    single_num = num
                    
                    count = 1
                
                elif count == 1:
                    print "count", count
                    
                    print "num", num
                    
                    print "single num", single_num
                    
                    return single_num
            elif single_num == num:
                count += 1
            
            if i >= len(A)-1:
                return single_num

In [104]:
print solution_5(A)


count 1
num 9
single num 7
7

In [106]:
1 % 2


Out[106]:
1

V5 .1


In [109]:
def solution_5_1(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 0
            
        for i,num in enumerate(sorted(A)):
            if num != single_num:    
                if count % 2:
                    print "count", count
                    
                    print "num", num
                    
                    print "single num", single_num
                    
                    return single_num
                
                single_num = num
                
                count = 1
                
            elif single_num == num:
                count += 1
            
            if i >= len(A)-1:
                return single_num

In [111]:
print solution_5_1(A)


count 1
num 9
single num 7
7

V 5_2


In [113]:
def solution_5_2(A):
    
    if len(A) == 0:
        return A
    
    elif len(A) == 1:
        return A[0]
    
    elif type(A) is int:
        return A
    
    elif len(A) % 2:
        single_num = sorted(A)[0]
        
        count = 0
            
        for i,num in enumerate(sorted(A)):
            if num != single_num:    
                if count % 2:            
                    return single_num
                else:
                    single_num = num
                
                    count = 1
                
            elif single_num == num:
                count += 1
            
            if i >= len(A)-1:   
                if count % 2:            
                    return single_num
                else
                    #just in case-
                    return None

In [115]:
print solution_5_2(A)


7

In [ ]: